﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphTheory.Task1
{
    class WeightedDigraph
    {
        public int[] Vertices { get; private set; }
        public int[,] AdjacencyMatrix { get; private set; }
        public int[,] WeightMatrix { get; private set; }

        public WeightedDigraph(int[] Vertices, int[,] AdjacencyMatrix, int[,] WeightMatrix)
        {
            this.Vertices = Vertices;
            this.AdjacencyMatrix = AdjacencyMatrix;
            this.WeightMatrix = WeightMatrix;
        }

        public WeightedDigraph(int VerticesAmount, int[,] AdjacencyMatrix, int[,] WeightMatrix)
        {
            this.Vertices = new int[VerticesAmount];
            for (int i = 0; i < VerticesAmount; i++)
            {
                this.Vertices[i] = i;
            }
            this.AdjacencyMatrix = AdjacencyMatrix;
            this.WeightMatrix = WeightMatrix;
        }

        public static WeightedDigraph ParseFromString(string str)
        {
            StringScanner scanner = new StringScanner(str);
            int VerticesAmount = scanner.nextInt();
            int[,] AdjacencyMatrix = new int[VerticesAmount, VerticesAmount];
            int[,] WeightMatrix = new int[VerticesAmount, VerticesAmount];

            for (int i = 0; i < VerticesAmount; i++)
            {
                for (int j = 0; j < VerticesAmount; j++)
                {
                    AdjacencyMatrix[i, j] = scanner.nextInt();
                }
            }

            for (int i = 0; i < VerticesAmount; i++)
            {
                for (int j = 0; j < VerticesAmount; j++)
                {
                    WeightMatrix[i, j] = scanner.nextInt();
                }
            }

            return new WeightedDigraph(VerticesAmount, AdjacencyMatrix, WeightMatrix);
        }



        public int[,] GetMaxFlows(int source, int sink)
        {
            int[,] flows = new int[this.Vertices.Length, this.Vertices.Length];
            for (int i = 0; i < this.Vertices.Length; i++)
            {
                for (int j = 0; j < this.Vertices.Length; j++)
                {
                    flows[i, j] = 0;
                }
            }

            while (true)
            {
                Tuple<int, int>[] Marks = GetMarks(flows, source, sink);
                if (Marks[GetIndex(this.Vertices, sink)] == null)
                {
                    return flows;
                }

                //int min = 
                int currentVertex = sink;
                int dobavochka = Math.Abs(Marks[GetIndex(this.Vertices, sink)].Item2);
                int vrt;
                do
                {
                    int currentIndex = GetIndex(this.Vertices, currentVertex);
                    Tuple<int, int> mark = Marks[currentIndex];
                    vrt = mark.Item1;
                    int index = GetIndex(this.Vertices, vrt);
                    if (mark.Item2 > 0)
                    {
                        flows[index, currentIndex] += dobavochka;
                    }
                    else
                    {
                        flows[currentIndex, index] -= dobavochka;
                    }
                    currentVertex = vrt;
                } while (vrt != source);
            }


        }

        public Tuple<int, int>[] GetMarks(int[,] flows, int source, int sink)
        {
            Tuple<int, int>[] Marks = new Tuple<int, int>[this.Vertices.Length];
            List<int> NotViewed = this.Vertices.ToList();
            List<int> Marked = new List<int>();

            int max = 1;

            for (int i = 0; i < this.Vertices.Length; i++)
            {
                for (int j = 0; j < this.Vertices.Length; j++)
                {
                    max += (this.WeightMatrix[i, j] >= 0 ? this.WeightMatrix[i, j] : -this.WeightMatrix[i, j]);
                }
            }

            Marks[GetIndex(this.Vertices, source)] = new Tuple<int, int>(source, max);
            Marked.Add(source);
            while(GetIntersect(Marked, NotViewed).Count != 0)
            {
                int currentVertex = GetIntersect(Marked, NotViewed).First();
                int currentIndex = GetIndex(this.Vertices, currentVertex);
                List<int> outgoing = GetIntersect(GetOutgoingVertices(this, currentVertex), NotViewed);
                foreach (var vertex in outgoing)
                {
                    int index = GetIndex(this.Vertices, vertex);
                    int difference = this.GetArcWeight(currentVertex, vertex) - flows[currentIndex, index];
                    if (difference > 0)
                    {
                        int min = (Math.Abs(Marks[currentIndex].Item2) <= difference)? Math.Abs(Marks[currentIndex].Item2):difference;
                        Marks[index] = new Tuple<int, int>(currentVertex, min);
                        if (!Marked.Contains(vertex))
                        {
                            Marked.Add(vertex);
                        }
                    }
                }

                List<int> ingoing = GetIntersect(GetIngoingVertices(this, currentVertex), NotViewed);
                foreach (var vertex in ingoing)
                {
                    int index = GetIndex(this.Vertices, vertex);
                    int flow = flows[index, currentIndex];
                    if (flow > 0)
                    {
                        int min = (Math.Abs(Marks[currentIndex].Item2) <= flow) ? Math.Abs(Marks[currentIndex].Item2) : flow;
                        Marks[index] = new Tuple<int, int>(currentVertex, - min);
                        if (!Marked.Contains(vertex))
                        {
                            Marked.Add(vertex);
                        }
                    }
                }
                NotViewed.Remove(currentVertex);
            }
            return Marks;
        }

        private static int GetIndex(int[] Vertices, int vrt)
        {
            for (int i = 0; i < Vertices.Length; i++)
            {
                if (Vertices[i] == vrt)
                {
                    return i;
                }
            }
            throw new ArgumentException();
        }

        public int computeLength(int[] path)
        {
            int res = 0;
            for (int i = 0; i < path.Length - 1; i++)
            {

                res += this.GetArcWeight(path[i], path[i + 1]);
            }
            return res;
        }

        public static List<int> GetOutgoingVertices(WeightedDigraph digraph, int vertex)
        {
            int index = GetIndex(digraph.Vertices, vertex);
            List<int> res = new List<int>();
            for (int j = 0; j < digraph.Vertices.Length; j++)
            {
                if (digraph.AdjacencyMatrix[index, j] == 1)
                {
                    res.Add(digraph.Vertices[j]);
                }
            }

            return res;
        }

        public static List<int> GetIngoingVertices(WeightedDigraph digraph, int vertex)
        {
            int index = GetIndex(digraph.Vertices, vertex);
            List<int> res = new List<int>();
            for (int i = 0; i < digraph.Vertices.Length; i++)
            {
                if (digraph.AdjacencyMatrix[i, index] == 1)
                {
                    res.Add(digraph.Vertices[i]);
                }
            }

            return res;
        }

        public void AddArc(int source, int sink, int weight)
        {
            int indexSource = GetIndex(this.Vertices, source);
            int indexSink = GetIndex(this.Vertices, sink);
            this.AdjacencyMatrix[indexSource, indexSink] = 1;
            this.WeightMatrix[indexSource, indexSink] = weight;
        }

        public Tuple<int, int, int> DeleteArc(int source, int sink)
        {
            int indexSource = GetIndex(this.Vertices, source);
            int indexSink = GetIndex(this.Vertices, sink);
            this.AdjacencyMatrix[indexSource, indexSink] = 0;
            int weight = this.WeightMatrix[indexSource, indexSink];
            this.WeightMatrix[indexSource, indexSink] = 0;
            return new Tuple<int,int,int>(source, sink, weight);
        }

        public int GetArcWeight(int source, int sink)
        {
            int indexSource = GetIndex(this.Vertices, source);
            int indexSink = GetIndex(this.Vertices, sink);
            return this.WeightMatrix[indexSource, indexSink];
        }

        private static bool ContainsRoot(int[] path, int[] root)
        {
            if (path.Length < root.Length)
            {
                return false;
            }

            for (int i = 0; i < root.Length; i++)
            {
                if (path[i] != root[i])
                {
                    return false;
                }
            }
            return true;
        }

        private static List<int> GetIntersect(List<int> list1, List<int> list2)
        {
            List<int> res = new List<int>();
            foreach (var vertex in list1)
            {
                if (list2.Contains(vertex))
                {
                    res.Add(vertex);
                }
            }
            return res;
        }
    }
}
